package com.jason.library.algorithm;

/**
 * @author ChenBaoyang
 * @description: AlgorithmMain
 * @date 2021/8/20 10:33
 */
public class AlgorithmMain {


    public static void main(String[] args) {
        int[] coins = { 3, 7 };
        int amount = 22;
        int num = coinsChange(coins, amount, coins.length);
        System.out.println(num);
    }

    /**
     * 最小硬币算法
     * @param coins
     * @param amount
     * @param coinSize
     * @return
     */
    public static int coinsChange(int[] coins, int amount, int coinSize) {
        if (null == coins || amount == 0) {
            return -1;
        }

        int[] temp = new int[amount + 1];
        for (int i = 0; i <= amount; i++) {
            temp[i] = amount + 1;
        }
        //第一个设置为0
        temp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coinSize; j++) {
                System.out.println("原来的值：temp["+i+"] = "+temp[i]+", coins["+j+"] = "+coins[j]);
                if (i >= coins[j]) {
                    temp[i] = Math.min(temp[i], 1 + temp[i - coins[j]]);
                    System.out.println("变动后的值：temp["+i+"] = "+temp[i]+", coins["+j+"] = "+coins[j]);
                }

            }
        }
        return temp[amount] > amount ? -1 : temp[amount];
    }


}
